/*
https://leetcode-cn.com/problems/smallest-good-base/solution/zui-xiao-hao-jin-zhi-by-leetcode-solutio-csqn/
 */
public class Solution483 {
    public String smallestGoodBase(String n) {
        long num=Long.parseLong(n);
        int mMax=(int)(Math.log(num)/Math.log(2));
        for (int i=mMax;i>1;i--){
            int k=(int) Math.pow(num,1.0/i);
            long sum=1,mul=1;
            for (int p=0;p<i;p++){
                mul*=k;
                sum+=mul;
            }
            if (sum==num){
                return String.valueOf(k);
            }
        }
        return String.valueOf(num-1);
    }

    public static void main(String[] args) {
        System.out.println(new Solution483().smallestGoodBase("4681"));
    }
}
